package leetcode_1101_1200;

import java.util.*;

public class LeeCode_1125_timeout {
    public static void main(String[] args) {
        List<List<String>> p1 = new ArrayList<>();
        ArrayList<String> p11 = new ArrayList<>();
        p11.add("java");
        p1.add(p11);
        ArrayList<String> p12 = new ArrayList<>();
        p12.add("nodejs");
        p1.add(p12);
        ArrayList<String> p13 = new ArrayList<>();
        p13.add("nodejs");
        p13.add("reactjs");
        p1.add(p13);
        int[] ans1 = smallestSufficientTeam(new String[]{"java", "nodejs", "reactjs"}, p1);
        System.out.println(Arrays.toString(ans1));
    }
    private static int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
        int n = req_skills.length;
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(req_skills[i], i);
        }
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < people.size(); i++) {
            List<String> skills = people.get(i);
            for (String skill : skills) {
                list.get(map.get(skill)).add(i);
            }
        }
        int[] min = new int[1];
        min[0] = Integer.MAX_VALUE;
        Map<Integer, List<Integer>> ans = new HashMap<>();
        List<Integer> now = new ArrayList<>();
        dfs(list, 0, min, ans, now);
        List<Integer> res0 = ans.get(min[0]);
        int[] res = new int[res0.size()];
        for (int i = 0; i < res0.size(); i++) {
            res[i] = res0.get(i);
        }
        return res;
    }
    private static void dfs(List<List<Integer>> list, int index, int[] min,
                            Map<Integer, List<Integer>> ans, List<Integer> now){
        if (index >= list.size()){
            if (now.size() < min[0]){
                min[0] = now.size();
                ans.put(now.size(), now);
            }
            return;
        }
        List<Integer> ps = list.get(index);
        for (int peo : ps) {
            List<Integer> newNow = new ArrayList<>(now);
            if (!now.contains(peo)){
                newNow.add(peo);
            }
            dfs(list, index + 1, min, ans, newNow);
        }
    }
}
